import datastructure.linklist.ListNode;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/4 10:03
 * @description:
 */
public class Solution206 {
    //1 -> 2 -> 3 -> null    null <- 1 <- 2 <- 3
    // 头插法(迭代法)
    //pre 指向链表的头，cur是要连接的结点，next是要连接的结点的下一个结点
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;//下一个结点
            cur.next=pre;
            pre = cur;
            cur=next;
        }
        return pre;
    }
    //递归法:假设2-3已经翻转
    public ListNode reverseList2(ListNode head) {
        if(head==null || head.next ==null){
            return head;
        }
        ListNode newHead = reverseList2(head.next);
        head.next.next=head;
        head.next=null;
        return newHead;
    }


    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        ListNode head = ListNode.arrayToList(nums);
        Solution206 solution = new Solution206();
        ListNode newHead = solution.reverseList2(head);
        ListNode.printListWithCycleCheck(newHead);
    }
}
